package problem;

import java.util.*;


/**
 * 问题描述：如有一数n,其真因数的总和等于n ，称之为完美数。
 * 解法：
 * 		1. 求出一定数目的质数表
 * 		2. 利用质数表求指定数的因式分解
 * 		3. 利用因式分解求所有真因数和，并检查是否为完美数。
 * 步骤3
 * 		2*28 = (2^0+2^1+2^2)(7^0+7^1)
 * @author Jun
 *
 */
public class PerfectNumber {

	
	 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		for(Integer number : lessThan(1000)){
			System.out.print(number+ " ");
		}
	}

	/**
	 * Return the list of no less than number
	 * @param number
	 * @return
	 */
	public static List<Integer> lessThan(int number) {
		 
		
		List<Integer> list = new ArrayList<Integer>();
		List<Integer> primes = Prime.findPrimes(number);
		for(int i = 1; i <= number; i++) { 
            if(i == sum(factor(primes, i))) 
                list.add(i);
        } 
		
		
		return list;
	 }
	
	/**
	 * 以28为例，得到的list: 
	 * 		[2,2,7,1]
	 * @param primes
	 * @param n
	 * @return
	 */
	public static List<Integer> factor(List<Integer> primes, int n) {
		
		List<Integer> factor = new ArrayList<Integer>();
		
//		for(int prime : primes){			
//			if(n/prime == 0 ) factor.add(prime);			
//		}
		int tmp = 0;
		for(int i = 0; primes.get(i)< Math.sqrt(n);){
			tmp = primes.get(i);
			if( n% tmp ==0){
				factor.add(tmp);
				n /= tmp;
			}
			else {
				i++; 
			}
		}
		
		//1或者质数本身
		factor.add(n);
		return factor;
	}
	 
	/**
	 * @param factors
	 * @return
	 */
	private static int sum(List<Integer> factors) { 
		
		int sum = 1;
		int i = 0;
		int size = factors.size();
		
		while(i< size){
			
			int sfsum = 1;
			int factor = 1;
			
			do{
				factor *= factors.get(i);
				sfsum += factor;
				i++;				
			}while(i<size-1 && (factors.get(i-1).equals(factors.get(i))));
			
			sum *= sfsum;
		}
		
		return sum/2;
	}
	

}
